`:top

Die `F33f`_`[Komplexitätsklasse`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Komplexitätsklasse]`_`f `!#P`! (`F33f`_`[englische`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Englische_Sprache]`_`f Aussprache `*Sharp-P`* oder `*Number-P`*) ist eine Klasse von sogenannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die `F33f`_`[Entscheidbar`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Entscheidbar]`_`f behandeln). Viele #P-Probleme sind eng verwandt mit den zugehörigen `F33f`_`[NP`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=NP_(Komplexitätsklasse)]`_`f-Problemen.

Die Klasse wurde 1979 von `F33f`_`[Leslie Valiant`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Leslie_Valiant]`_`f eingeführt.

>>Contents

• `F0af`_`[Definition`#definition]`_`f

• `F0af`_`[Beispiel`#beispiel]`_`f

• `F0af`_`[Eigenschaften`#eigenschaften]`_`f

• `F0af`_`[Liste einiger #P-vollständiger Probleme`#liste-einiger-p-vollst-ndiger-probleme]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Weblinks`#weblinks]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Definition

Ein Problem ist in der Klasse #P, wenn eine `F33f`_`[nichtdeterministische Turingmaschine`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nichtdeterministische_Turingmaschine]`_`f existiert, die `F33f`_`[polynomiell zeitbeschränkt`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Polynomialzeit]`_`f ist und für jede Instanz I {\\displaystyle I} des Problems genau so viele akzeptierende Berechnungspfade hat, wie es Lösungen zu der Instanz I {\\displaystyle I} gibt.

>>Beispiel

Ein bekanntes Entscheidungsproblem aus NP ist das `F33f`_`[Erfüllbarkeitsproblem der Aussagenlogik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Erfüllbarkeitsproblem_der_Aussagenlogik]`_`f (SAT):

• Existiert zu einer gegebenen aussagenlogischen Formel eine erfüllende Variablenbelegung?

Das zugehörige Zählproblem aus #P wird mit #SAT bezeichnet und lautet:

• Wie viele erfüllende Variablenbelegungen gibt es zu einer gegebenen aussagenlogischen Formel?

>>Eigenschaften

Nach dem Satz von Toda`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] reichen deterministische polynomiell zeitbeschränkte Turingmaschinen, die eine einzige `F33f`_`[Orakel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Orakel-Turingmaschine]`_`f-Anfrage an ein Problem aus #P stellen dürfen, um die Sprachen in `F33f`_`[PH`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Polynomialzeithierarchie]`_`f zu entscheiden. Dies ist ein Hinweis für die enorme Schwierigkeit, #P-Probleme exakt zu lösen. Andererseits kann in polynomiellem Platz der Berechnungsbaum einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine vollständig durchsucht werden, so dass sich alle #P-Probleme in polynomiellen Platz berechnen lassen. Damit lässt sich #P wie folgt in Beziehung zu anderen wichtigen Komplexitätsklassen setzen:

`F33f`_`[P`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=P_(Komplexitätsklasse)]`_`f ⊆ `F33f`_`[NP`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=NP_(Komplexitätsklasse)]`_`f ⊆ `F33f`_`[PH`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Polynomialzeithierarchie]`_`f ⊆ P#P ⊆ `F33f`_`[PSPACE`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=PSPACE]`_`f

Da #P die Komplexitätsklasse NP enthält sind sie mindestens so schwer zu lösen.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>Liste einiger #P-vollständiger Probleme

• #SAT

• Anzahl der `F33f`_`[perfekten Matchings`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Matching_(Graphentheorie)]`_`f eines `F33f`_`[bipartiten Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bipartiter_Graph]`_`f

Diese Tatsache ist besonders interessant, weil das zugehörige Entscheidungsproblem (`*Existenz`* von perfekten Matchings in bipartiten Graphen) deterministisch in polynomieller Zeit lösbar ist (also in P ist).

• Gibt es ein perfektes Matching in einem allgemeinen Graphen ? Das Problem ist auch in P lösbar.`:cite-ref-cai-3-0[`F5bf`_`[3`#cite-note-cai-3]`_`f]

• `F33f`_`[Permanente`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Permanente]`_`f (einer 0-1-Matrix)

• Anzahl der linearen Erweiterungen einer partiellen Ordnung.

>>Literatur

• Leslie G. Valiant: `*The complexity of computing the permanent`*. Theoretical Computer Science, 8:189-201, 1979

• Graham Brightwell, Peter Winkler: Counting linear extensions, Order, Volume 8, Issue 3, Sep 1991, Pages 225 - 242, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1007/BF00383444

>>Weblinks

• `*#P.`* In: `*Complexity Zoo.`* (englisch)

>>Einzelnachweise

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `F33f`_`[Seinosuke Toda`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Seinosuke_Toda]`_`f, `*PP is as Hard as the Polynomial-Time Hierarchy,`* SIAM Journal on Computing, Band 20, 1991, S. 865–877

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13

`:cite-note-cai-3`!3.`! `F0af`_`[↑`#cite-ref-cai-3-0]`_`f `F33f`_`[Jin-Yi Cai`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Jin-Yi_Cai]`_`f, `*Computational Complexity and Holographic Algorithms`*, Vortragsfolien, Abrufbar von Jin-Yi Cai der Webseite von Cai als `*Talk at MIT and Brown 2008 on Holographic Algorithms`*

`c`F0af`_`[↑ Back to top`#top]`_`f`a